package com.example.question.dp.dp2;

import java.util.Arrays;

public class Code09_377 {
    public static void main(String[] args) {
        Code09_377 code = new Code09_377();
        int ret = code.combinationSum4(new int[]{10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150, 160, 170, 180, 190, 200, 210, 220, 230, 240, 250, 260, 270, 280, 290, 300, 310, 320, 330, 340, 350, 360, 370, 380, 390, 400, 410, 420, 430, 440, 450, 460, 470, 480, 490, 500, 510, 520, 530, 540, 550, 560, 570, 580, 590, 600, 610, 620, 630, 640, 650, 660, 670, 680, 690, 700, 710, 720, 730, 740, 750, 760, 770, 780, 790, 800, 810, 820, 830, 840, 850, 860, 870, 880, 890, 900, 910, 920, 930, 940, 950, 960, 970, 980, 990, 111}, 999);
        System.out.println(ret);
        System.out.println("code.combinationSum4(new int[]{1, 2, 3}, 4) = " + code.combinationSum4(new int[]{1, 2, 3}, 7));
    }


    public int dfs(int[] nums, int target, int index, int[][] memo) {
        if (target < 0) {
            return -1;
        }
        // 边界条件
        if (target == 0) {
            return 1;
        }
        if (memo[index][target] != 0) {
            return memo[index][target];
        }
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            int dfs = dfs(nums, target - nums[i], i, memo);
            if (dfs != -1) {
                sum += dfs;
            }
        }
        memo[index][target] = sum;
        return memo[index][target];
    }

    public int combinationSum4(int[] nums, int target) {
        int f = f(nums, target);
        return f == Integer.MAX_VALUE ? 0 : f;
    }


    /**
     * 这个感觉是是二维的  是如何推导优化成一维的 还需要分析分析
     */
    public int f(int[] nums, int target) {
        int[] dp = new int[target + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        for (int j : nums) {
            if (j <= target) {
                dp[j] = 1;
            }
        }
        for (int i = 0; i <= target; i++) {
            int sum = 0;
            boolean flag = false;
            for (int num : nums) {
                if (i > num && dp[i - num] != Integer.MAX_VALUE) {
                    flag = true;
                    sum += dp[i - num];
                }
            }
            if (flag) {
                if (dp[i] == 1) {
                    sum += 1;
                }
                dp[i] = sum;
            }
        }
        return dp[target];
    }
}
